package leetcode;
/**
 * 572.另一棵树的子树
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 *
 * 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
 * 输出：true
 * 输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
 * 输出：false
 */
public class Num_572 {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //边界条件
        if(root == null && subRoot == null){
            return true;
        }
        if(root == null ^ subRoot == null){
            return false;
        }
        //p和q是否为相同的树 || p的左子树是否包含q || p的右子树是否包含q
        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) ||isSubtree(root.right,subRoot);
    }
    //判断两个数是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //都为空，返回true
        if(p == null && q == null){
            return true;
        }
        //一个为空，另一个不为空，返回false
        if(p == null ^ q == null){
            return false;
        }
        //两个节点值相同 && 每个节点子树对应的位置节点也相同
        return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}
